package listbyorder.access101_200.test123;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/15 11:14
 */
public class Solution3 {

    // 方法三 动态规划
    // 用 dp[i][k] 表示前i天最多交易k次的最高收益
    // 在第 0 天买入，收益就是 prices[i] - prices[0]
    // 在第 1 天买入，收益就是 prices[i] - prices[1] + dp[0][k-1]，多加了前一天的最大收益
    // 在第 2 天买入，收益就是 prices[i] - prices[2] + dp[1][k-1]，多加了前一天的最大收益
    // ...
    // 在第 j 天买入，收益就是 prices[i] - prices[j] + dp[j-1][k-1]，多加了前一天的最大收益
    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }

        int K = 2;
        int[][] dp = new int[prices.length][K + 1];

        for (int k = 1; k <= K; k++) {
            for (int i = 1; i < prices.length; i++) {
                int min = Integer.MAX_VALUE;
                for (int j = 0; j <= i; j++) {
                    // j表示在 第j天 的时候买入产品
                    min = Math.min(min, prices[j] - dp[j][k - 1]);
                }
                // 比较当前i位置不操作或者卖出的大小情况
                dp[i][k] = Math.max(dp[i - 1][k], prices[i] - min);
            }
        }

        return dp[prices.length - 1][2];
    }
}
